package com.example.algorithm.prefixSum;

import java.util.HashMap;
import java.util.Map;

/**
 * 给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。
 * 子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。
 * 如果 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 两个子矩阵中部分坐标不同（如：x1 != x1'），那么这两个子矩阵也不同。
 * <p>
 * 示例 1：
 * 输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
 * 输出：4
 * 解释：四个只含 0 的 1x1 子矩阵。
 * <p>
 * 示例 2：
 * 输入：matrix = [[1,-1],[-1,1]], target = 0
 * 输出：5
 * 解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。
 * <p>
 * 示例 3：
 * 输入：matrix = [[904]], target = 0
 * 输出：0
 */
public class Leetcode1074_NumSubmatrixSumTarget {
    static class Solution {
        /**
         * 前缀和 + 哈希表
         * 枚举两列之间(上下界分别记为 i1, i2)的列前缀和数组 tmpColSum
         *     则：tmpColSum[j] = sum(matrix[i][j])  其中 i1 <= i <= i2
         *     所以 以 (i1, j1)为左上角, (i2, j2)为右下角的矩形和可以表示为
         *     regionSum = sum(tmpColSum[0:j + 1]) - sum(tmpColSum[0:i])
         * @param matrix
         * @param target
         * @return
         */
        public int numSubmatrixSumTarget(int[][] matrix, int target) {
            int m = matrix.length, n = matrix[0].length, res = 0;
            for (int i1 = 0; i1 < m; i1++) {
                int[] tmpColSum = new int[n];  // tmpColSum[j] 表示 从 i1 到 i2 的第 j 列的和
                for (int i2 = i1; i2 < m; i2++) {
                    for (int j = 0; j < n; j++) {
                        tmpColSum[j] += matrix[i2][j];
                    }
                    res += subArraySum(tmpColSum, target);
                }
            }
            return res;
        }

        private int subArraySum(int[] nums, int target) {
            int preSum = 0, count = 0;
            Map<Integer, Integer> map = new HashMap<>(); // key: 前缀和， value:前缀和的个数
            map.put(0, 1);
            for (int num : nums) {
                preSum += num;
                count += map.getOrDefault(preSum - target, 0);
                map.put(preSum, map.getOrDefault(preSum, 0) + 1);
            }
            return count;
        }
    }

    public static void main(String[] args) {
        int[][] matrix = {{0, 1, 0}, {1, 1, 1}, {0, 1, 0}};
        int target = 0;

        matrix = new int[][] {{1, -1}, {-1, 1}};
        target = 0;
        System.out.println(new Solution().numSubmatrixSumTarget(matrix, target));
    }
}
